In database systems, many resources (such as data blocks, tables, indexes) are shared among multiple processes. Even though resources may be shared, many resources may not be used by more than one process at a given time. For example, sometimes, tables stored on a storage medium may be concurrently accessed in some ways (e.g., read) by multiple processes, but accessed in other ways (e.g., written to) by only one process at a time. As a result, mechanisms have been developed to control access to resources.
One such mechanism uses locks. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to a resource. There are many types of locks, some of which may be shared by many processes, while other types prevent any other locks from being granted on the same resource.
When multiples processes require multiple locks on different resource simultaneously, a deadlock situation may arise. Generally, a deadlock occurs when two or more processes are each waiting for another process to release a resource. For example, process A might hold a lock on resource A′, and process B might hold a lock on resource B′. Process A might request, on resource B′, a lock that is incompatible with the current lock on resource B′. Two locks are incompatible with respect to each other if one lock on a resource prevents a process from acquiring the other lock on the resource. Similarly, process B requests a lock on resource A′ that is incompatible with the current lock on resource A′. Under these circumstances, if process A and process B are “willing” to wait indefinitely for the current locks to be released, then process A and process B are said to be deadlocked with respect to each other.
According to one approach, a process is configured to abort and return an error if the process requests, on a resource, a lock that is incompatible with a current lock on the resource. In high traffic database systems, however, returning errors causes delays and, as a result, users experiences to suffer. It may be important to ensure that most (if not all) database transactions are processed without noticeable delays.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.